package com.xq.algorithm.sort;

import static com.xq.algorithm.AlgorithmTest.printlnAry;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/09.
 *         归并排序
 *         是创建在归并操作上的一种有效的排序算法该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
 *         速度仅次于快速排序，为稳定排序算法（即相等的元素的顺序不会改变），一般用于对总体无序，但是各子项相对有序的数列.
 */

public class MergeSortAlgorithm {

    /**
     * 归并排序
     * @param nums
     * @param low
     * @param hight
     * @return
     * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，
     * 每个子序列是有序的。然后再把有序子序列合并为整体有序序列
     * 时间复杂度为O(nlogn) 　 　　 　　空间复杂度为 O(n)
     * 稳定排序方式
     */
    public static int[] mergeSort(int[] nums,int low, int hight){
        int mid = (low + hight) / 2;
        if(low < hight){
            //左边
            mergeSort(nums,low,mid);
            //右边
            mergeSort(nums,mid + 1, hight);
            //左右归并
            merge(nums,low,mid,hight);
        }
        return nums;
    }

    /**
     * 合并为整体有序序列
     * @param nums
     * @param low
     * @param mid
     * @param hight
     *
     */
    public static void merge(int[] nums,int low,int mid,int hight){
        int[] temp = new int[hight - low + 1];
        int i = low; //左指针
        int j = mid + 1; //右指针
        int k = 0;

        //把较小的数先移到新数组中
        while (i < mid && j <= hight){
            if(nums[i] < nums[j]){
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
            }
        }

        //把左边剩余的数移入数组
        while (i <= mid){
            temp[k++] = nums[i++];
        }

        //把右边剩余的数移入数组
        while (j <= hight){
            temp[k++] = nums[j++];
        }

        // 把新数组中的数覆盖nums数组
        for(int k2 = 0; k2 < temp.length; k2++){
            nums[k2 + low] = temp[k2];
        }
    }

    public static void testMergeSort(){
        int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };
        printlnAry(nums);
        mergeSort(nums,0,nums.length - 1);
        printlnAry(nums);
    }
}
